 /*
 =====================================================================================
 *       Filename:  myqsort.cpp
 *
 *    Description:  qsort with my own realization.
 *
 *        Version:  1.0
 *        Created:  2012/2/22 19:40:17
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Zhigang Wang, 
 *   Organization:  test of Youdao
 *
 * =====================================================================================
*/
#include <iostream>
#include <algorithm>
#include <stack>
 
using namespace std;

typedef std::stack<int> Stack;
void show_array(int * array,int n);
int  partition( int *array, int p ,int r );
void myqsort(int *array, int p ,int r);
void qsort_without_recursion(int* array, int p, int r);

void show_array(int * array,int n){
//show data values in the array;
  for(int i = 0; i < n; i++)
      cout<<array[i]<<' ';
  cout<<endl;
}

int partition( int *array, int p ,int r ){
//find the proper positon for array[p]
  int x;
  x = array[p];
  while( p < r ){
    while( p < r && array[r] >= x)
      r--;
    swap(array[p] ,array[r]);
    while( p <r  && array[p] <= x) 
      p++;
    swap(array[p], array[r]);
  }
  return p;
}
void qsort_with_recusion(int *array, int p ,int r){
  int q;
  if(p < r){
    q = partition(array,p,r);
    qsort_with_recusion(array, p, q - 1);
    qsort_with_recusion(array, q + 1, r);
  }
}
void qsort_without_recursion(int* array, int p, int r)
{
    Stack st;
    int temp;
    if(p < r){
     int q = partition(array, p, r);
     st.push(p);
     st.push(q - 1); 
     st.push(q + 1);
     st.push(r);   
     while(!st.empty()) {
        r = st.top();
        st.pop();
        p = st.top();
        st.pop();                    
        if(p < r){
            q = partition(array, p, r);                           
            temp = q - 1;
            if(p < temp){
               st.push(p);
               st.push(temp);
             } 
             temp = q + 1;
             if(temp < r){
                st.push(temp);
                st.push(r);
              }
          }
      }
    } 
}
int main(){
/* testcode 
  int a[]={10,9,6,7,8,5,4,3,2,1};
  qsort_without_recursion(a,0,9);
  show_array(a,10);
*/
  return 0;
}

